Day10. 佇列(Queue)與堆疊(Stack)

15th鐵人賽

雜食性的貓

2023-09-25 23:17:56

553 瀏覽

分享至

資料結構

佇列和堆疊這兩種資料結構常常被放在一起比較，一如陣列與鏈結串列一樣，因為他們的結構處理的問題有一定程度的相似，卻在特性上迥然相異。兩者比起陣列和鏈結串列，都多了能夠將儲存的元素排出的方法，而兩者的差異也就正在這方法上。

白話的說佇列就像排隊買東西，結帳的隊伍是佇列，先進的人(資料)，在出去的時候就會先離開隊伍。
堆疊一如今天的圖，就是疊在一起，先進的資料(如圖的最下面的狗)，得等上面的資料離開，才能出去，後進的會先出去。
FIFO，First In First Out ─ 佇列
FILO，First In Last Out - 堆疊。

在大多語言都有實現這兩個類別，C#也是，宣告方式如下：

Queue<int> intq = new Queue<int>();
Stack<int> ints = new Stack<int>();

<>為泛型，可以依照需求放入類別。
大小方面比較類似鏈結串列，無須在開始時定義，可直接對資料結構做插入或排出元素。

基本操作

Queue 和 Stack 的操作也是大同小異，主要差異體現在上面提到的順序：
Queue

Enqueue : 把元素放到佇列的最尾端
Dequeue : 把佇列最前端的元素從佇列移除並回傳
Peek : 回傳佇列最前端的元素，但並不移除

Stack

Push : 把元素放到堆疊的頂端
Pop : 把堆疊最頂端的元素從堆疊移除並回傳
Peek : 回傳堆疊最頂端的元素，但並不移除

這些操作的時間複雜度都為 O(1)。
一如他們的特性，Queue 適合用於正序處理元素的情況，如廣度優先搜尋(BFS)，而 Stack 適合用於反向處理元素的情況，如深度優先搜尋(DFS)，關於 BFS 和 DFS，我們會在後面聊到樹的章節後再來細看。

互相模擬

在 Leetcode 有題目是用 Queue 模擬 Stack，和反過來的用 Stack 模擬 Queue，我們今天來看這兩道題目，寫完兩道題目，應該會對這兩個資料結構的操作更有把握。

Implement Queue using Stacks

首先是使用 Stack 來模擬 Queue 的行為。總共要實現 push、pop、peek 和 empty 這幾個函式。
Stack 是後進先出，Queue 是先進先出，所以遇到的難題是，先進被堆疊在底下的元素，怎麼先出？可以想見這邊會需要一個反序的操作，讓後進先出順序反過來，才能夠變成先進先出。
我們直接分享小技巧寫法，當然硬寫一定寫得出來，但有優雅的方式可以解決這個問題：兩個 Stack。
一個 Stack 負責被添加元素，一個 Stack 負責出元素，接下來用 inStack 和 outStack 來稱呼。

運作原理是，當 push 的時候，元素進去 inStack，pop 的時候，把 inStack 所有元素倒進去 outStack，此時 outStack 中的元素就變成先進先出的順序。但在倒進去之前，先檢查這個時候的 outStack 為不為空，因為 outStack 我們之前是從 inStack 反序倒過來的，已經整理成先進先出的順序了，此時如果有元素的情況下倒元素進來，順序就會亂掉。所以 pop 完整的實現應該是先檢查 outStack 為不為空，不為空直接 pop 第一個元素(保證 outStack 是先進先出的順序)，而如果 outStack 為空，則把 inStack 的元素倒進來，就能把本來先進後出反轉成先進先出，繼續 pop 第一個元素。

public class MyQueue {
    public Stack<int> inStack;
    public Stack<int> outStack;

    public MyQueue() {
        inStack = new Stack<int>();
        outStack = new Stack<int>();    
    }
    
    public void Push(int x) {
        inStack.Push(x);
    }
    
    public int Pop() {
        if(outStack.Count == 0){
            while(inStack.TryPop(out int val)){
                outStack.Push(val);
            }
        }
        return outStack.Pop();
    }
    
    public int Peek() {
        var val = Pop();
        outStack.Push(val);
        return val;
    }
    
    public bool Empty() {
        return inStack.Count == 0 && outStack.Count == 0;
    }
}

這邊另一個可以注意的是，Peek 如果按上面邏輯去寫，我們會寫出一個和 Pop 近乎一樣的程式碼，為了增加程式碼的可複用性，其實我們可以透過 Pop 和 Push 回去來實現 Peek。
Peek 就是不把元素移除的 Pop，所以我們先把元素 Pop 出來，知道是哪個元素後，放回 outStack裡，因為我們剛剛是從 outStack 拿元素的，這樣相當於我們復原了剛剛的操作，也拿到值，減少了重複程式碼的產生。

Implement Stack using Queues

至於用 Queue 實現 Stack，就沒有像上題的小技巧了，就是很直覺的把東西全部倒出來，再把非對像的裝回去。
可以想見假設現在有 1,2,3 依序放入 Queue 裡，要讓 Queue 模擬 Stack 做 Pop，那希望先傳出 3。
所以實現方法就是讓 1 移動到最尾變成 2,3,1，2 移動到最尾 3,1,2，此時最前的數做 Dequeue，就會是我們希望傳出的 3。也就是總共要進行 Count - 1 次的移動 Dequeue + Enqueue，最後做一次 Dequeue 就完成。

這題的巧思是在 Peek 上，Peek 在 Stack 上就是要知道「最後放入的元素」，所以我們可以透過維護一個最後放入的元素的變數，並在每次 Push 時更新，我們就不必連 Peek 都要重複 Pop 的重新 Dequeue + Enqueue 的操作了。但是，因為 Pop 把最後進入的元素拋出時，我們應該要修改 Pop 的程式碼，在 Count - 2 次移動(Queue 中倒數第二個元素)的時候更新維護的最後一個放入的元素的變數，然後一樣 Dequeue + Enqueue 回去，其餘操作不變，只是多一個刷新紀錄值的時間點。

public class MyStack {
    public Queue<int> queue;
    public int lastElementInQueue;

    public MyStack() {
        queue = new Queue<int>();     
    }
    
    public void Push(int x) {
        lastElementInQueue = x;
        queue.Enqueue(x);        
    }
    
    public int Pop() {
        var loop = queue.Count - 1;
        while(loop > 1){
            queue.Enqueue(queue.Dequeue());
            loop--;
        }
        lastElementInQueue = queue.Dequeue();
        queue.Enqueue(lastElementInQueue);

        return queue.Dequeue();
    }
    
    public int Top() {
        return lastElementInQueue;
    }
    
    public bool Empty() {
        return queue.Count == 0;
    }
}

大致上上面就是關於 Stack 和 Queue 相互實現的方式，也透過這兩題可以更加體認到兩個結構的差異和如何去注意兩個結構函式各自代表的意涵。

關於 BFS 和 DFS 像上面說的，會在後面介紹，也會是比較常用到這兩個結構的演算法。